# 力扣1135. 最低成本联通所有城市（来源：力扣）
# 给定 n 个城市和一些道路，返回联通所有城市的最低成本。如果无法联通，返回 -1。道路的成本由给定的城市对和成本构成。
def solve(n, connections):
    parent = [i for i in range(n)]
    def find(x):
        if parent[x] != x:
            return find(parent[x])
        return parent[x] 
    
    def union(x,y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootY] = rootX
            return True
        return False

    connections.sort(key=lambda x:x[2])  # 按照距离升序排列
    weights = 0
    for p,q,weight in connections:
        if union(p,q):
            weights += weight
    return weights

if __name__ == "__main__":
    s = solve(3, [[0, 1, 1], [0, 2, 2], [1, 2, 1]])  # 使用样例数据调用函数
    print(s)
